package 牛客.中等;

/**
 * 定义重复字符串是由两个相同的字符串首尾拼接而成。例如："abcabc" 是一个长度为 6
 * 的重复字符串，因为它由两个 "abc" 串拼接而成；"abcba" 不是重复字符串，因为它
 * 不能由两个相同的字符串拼接而成。
 * 给定一个字符串，请返回其最长重复子串的长度。
 * 若不存在任何重复字符子串，则返回 0。
 * 本题中子串的定义是字符串中一段连续的区间。
 * 数据范围：字符串长度不大于 10^310
 * 3
 * ，保证字符串一定由小写字母构成。
 * 进阶：空间复杂度 O(1)O(1)，时间复杂度 O(n^2)O(n
 * 2
 * )
 */
public class 最长重复子串_NC142 {

    public static void main(String[] args) {

        // 0 1 2 3
        System.out.println(solve("ababc"));

    }

    /**
     * 枚举起点和重复字符串一半长度+总结规律
     * 0 1 2 3 4
     * 如果起点为 i , 重复字符串一半长度范围为 [1,(len-i)/2]
     * 分别从字符串的 i 和 i+(len-i)/2 的位置开始往后比较 (len-i)/2 个字符
     */
    public static int solve(String a) {
        char[] chars = a.toCharArray();
        // 长度从最大到小枚举，遇见符合的直接返回
        for (int i = chars.length / 2; i >= 1; i--) {
            int idx = 0;
            while ((chars.length - idx) >= i * 2) {
                int b1 = idx, b2 = idx + i;
                int cnt = i;
                while (cnt > 0) {
                    if (chars[b1] != chars[b2]) {
                        break;
                    }
                    b1++;
                    b2++;
                    cnt--;
                }

                if (cnt == 0) {
                    return i * 2;
                }
                idx = b1 + 1;
            }
        }
        return 0;
    }

}
